/*
Copyleft 2006 by T.S.Yo
*/


package exp.majority;
import exp.util.*;
import java.util.*;
import ec.*;
import ec.util.*;
import ec.coevolve.*;
import ec.vector.*;
import ec.simple.*;

/* 
 * Majority.java
 * 
 * Created: 2006.11.03
 * By: T.S.Yo
 */

/**
 * Majority implements the Majority Function (1-D CA) problem.
 *
 * @author T.S.Yo
 * @version 1.0 
 */

//public class Majority extends MyExpProblem implements MyExpProblemForm
public class Majority extends Problem implements GroupedProblemForm
{
//----------------------------------------------------------------------
    /* Parameters for Problem*/
    public static final String R_SIZE = "rule-neighbour-size";
    public static final String C_SIZE = "configuration-length";
    public static final String T_SIZE = "test-sample-size";
    public static final String M_STEP = "max-iteration-step";
    public int r;
    public int N;
    public int nIC;
    public int M;
    public MF mf = new MF();
    public int[][] testPoints;
//----------------------------------------------------------------------
/** Setup parameters */
    public void setup(final EvolutionState state, final Parameter base)
    {
        // very important, remember this
        super.setup(state,base);
                
        //----------------------------------------------------------------------
        // Parameters for Majority Problem
        r = state.parameters.getInt(base.push(R_SIZE),null,1);
        if (r<1) state.output.fatal("Rule Neighbour Size must be an integer greater than 0"); 
        N = state.parameters.getInt(base.push(C_SIZE),null,1);
        if (N<1) state.output.fatal("Configuration Length must be an integer greater than 0"); 
        nIC = state.parameters.getInt(base.push(T_SIZE),null,1);
        if (nIC<1) state.output.fatal("Test Sample Size must be an integer greater than 0"); 
        M = state.parameters.getInt(base.push(M_STEP),null,1);
        if (M<1) state.output.fatal("Test Sample Size must be an integer greater than 0"); 

        /** Create test points */
        selectObjTP();
        
        //----------------------------------------------------------------------
        // CheckParameters
        /*
        int ruleLength = (int)Math.pow(2.,(double)(2*r+1));
        int gsize = state.parameters.getInt(base.push("pop.subpop.0.species.genome-size"),null,1);
        if(gsize > ruleLength)
        {
            System.out.print("\nGnome-size is larger than rule length,"+ruleLength+", use the later instead\n");
            gsize = ruleLength;
        }
        if(STPflag==TPOINT_ALL)
        {
            if(N<=31)
            {
                nIC = (int)Math.pow(2.,(double)N);
            }else{
                System.out.print("\nToo many configurations exist. Randomly generate"+nIC+"instead\n");
                STPflag=TPOINT_FIXED_RANDOM;
            }
        }
        System.out.println("Parameters: \nr = "+r+",  N = "+N+",  I = "+nIC+",  M = "+M);
        System.out.println("STP: "+STPflag+"    SCO: "+SCOflag);*/
    }
//----------------------------------------------------------------------
// Create objective test points for evaluation 
    public void selectObjTP()
    {
        if(N<31)
        {
            testPoints = mf.allIC_Generate(N);
        }else{
            testPoints = mf.IC_Generate(N,nIC);
        }
    }
//----------------------------------------------------------------------
// preprocess and postprocess
    public void preprocessPopulation( final EvolutionState state, Population pop )
    {
        // Set fitness = 0
        for( int i = 0 ; i < pop.subpops.length ; i++ )
            for( int j = 0 ; j < pop.subpops[i].individuals.length ; j++ )
                ((SimpleFitness)(pop.subpops[i].individuals[j].fitness)).setFitness( state, 0, false );
    }

    public void postprocessPopulation( final EvolutionState state, Population pop )
    {
        // Evaluate solutions againt objective test points
        int ntp = testPoints.length;
        int nsol = pop.subpops[1].individuals.length;
        float[] objf = evalObjFitness(state, pop);
        
        // Output obj/subj fitness
        MyExpOutput myout = new MyExpOutput(state);
        myout.printFit(state, pop, objf);

        // Set evluated = true
        for( int i = 0 ; i < pop.subpops.length ; i++ ){
            for( int j = 0 ; j < pop.subpops[i].individuals.length ; j++ )
            {
                pop.subpops[i].individuals[j].evaluated = true;
            }    
        }
    }
//----------------------------------------------------------------------
/** Evaluation */
  public int eval1on1(final int[] rule,
		              final int[] config)
  {
    int maj = (mf.sumIntArray(config)>(N/2) ? 1 : 0);
    int hit=(mf.checkConvergence(r,M,rule,config)[0]==maj? 1:0);
    return (hit);
  }

  public void evaluate(EvolutionState state,
                       Individual[] ind,
                       boolean[] updateFitness,
                       boolean countVictoriesOnly,
                       int threadnum)
  {
    // Check number of number individuals: two
    if( ind.length != 2 || updateFitness.length != 2 )
        state.output.fatal( "The Majority problem evaluates only two individuals at a time." );

    // Check genome type: boolean array
    if( ! ( ind[0] instanceof BitVectorIndividual ) )
        state.output.fatal( "The test-point individuals in Majority problem should be BitVectorIndividuals." );
    if( ! ( ind[1] instanceof BitVectorIndividual ) )
        state.output.fatal( "The solution individuals in Majority problem should be BitVectorIndividuals." );

    // Create an integer copy of configuration
    BitVectorIndividual temp = (BitVectorIndividual)ind[0];
    int[] conf = new int[temp.genome.length];
    for(int x=0; x<temp.genome.length; x++)
      conf[x] = (temp.genome[x] ? 1:0);

    // Create an integer copy of rule
    temp = (BitVectorIndividual)ind[1];
    int[] rule = new int[temp.genome.length];
    for(int x=0; x<temp.genome.length; x++)
      rule[x] = (temp.genome[x] ? 1:0);

    // Calculate interaction
    int interaction = eval1on1(rule,conf);
    
    // Update fitness
    //if( updateFitness[0] ){
    //    ((SimpleFitness)(ind[0].fitness)).setFitness( state, (float)(-interaction), false );
    //}
    if( updateFitness[1] ){
        ((SimpleFitness)(ind[1].fitness)).setFitness( state, (float)(interaction), false );
    }
  }
  
  // Evaluate objective fitness
  public float[] evalObjFitness( final EvolutionState state, 
                                 final Population pop )
  {
        // Evaluate solutions againt objective test points
        int ntp = testPoints.length;
        int nsol = pop.subpops[1].individuals.length;
        float[] objFit = new float[nsol];
        // For retrieving rules
        BitVectorIndividual temp = (BitVectorIndividual)pop.subpops[1].individuals[0];
        int[] rule = new int[temp.genome.length];
        // Evaluate through
        for (int j = 0; j<nsol; j++)
        {
            objFit[j] = 0;
            // Copy the solution
            temp = (BitVectorIndividual)pop.subpops[1].individuals[j];
            // tranform solution into int array
            for(int x=0; x<temp.genome.length; x++) rule[x] = (temp.genome[x] ? 1:0);
            // Use eval1on1 to get the fitness against each test point
            for (int i = 0; i < ntp; i++)
            {
               objFit[j] += (float)eval1on1(rule,testPoints[i]);  // number of TP solved
            }
            objFit[j] /= (float)ntp;  // normalized
        }
        return (objFit);
  }

//----------------------------------------------------------------------
/**  
Inner class: MF 
Purpose:
    For a one-dimensional Cellular Automata problem, we are interested in finding local rules for majority function (if more than half are 1's, then vote for 1, otherwise vote for 0), and these rules consider only the target bit and its neighbours.  Before looking for optimal rules, we would like to know how many steps, M, is required to make a bit string converge, with respect to the bit string length, N, and neighbours on each side to be considered, r.
    This small program generates random rules and random initial bit-strings to test how many times each rule needs to be applied to make the bit-strings converge into uniform bit-strings.

Ref: Mitchell, M., Crutchfield, J.P. & Hraber, P.T. (1994). Evolving cellular automata to perform computations: Mechanisms and impediments. Physica D, 75:361-391.    
**/
class MF
{
//----------------------------------------------------------------------
// Initializer
//----------------------------------------------------------------------
    /* Generate all initial configurations with length of n    */
    public int[][] allIC_Generate(final int n)
    {
        int[][] allIC;          // ICs to return
        int mIC;
        
        // If configuration-length is small enough, generate all rules
        if( n <= 16 )
        {
            System.out.print("\nTotally 2^"+n+" configurations exist, generate all....\n");
            mIC = (int)Math.pow(2.,(double)n);
            allIC = new int[mIC][];
            for(int i=0; i < mIC; i++)
            {
                // Convert i into n-bit binary string
                allIC[i] = intToBitArray(n,(int)i);
            }
        // If configuration-length is too large, generate configurations with multiple indexing in tree structure
        } else {
            System.out.print("\nTotally 2^"+n+" configurations exist. It is too big for indexing, randomly generate 100 instead\n");
            allIC = IC_Generate(n,100);
        }        
         
        return allIC;
    }

    /* Randomly generate nIC initial configurations:
         n      : length of configuration
         nIC    : number of configurations wanted*/
    public int[][] IC_Generate(final int n, final int nIC)
    {
        int[][] allIC;          // ICs to return
        int mIC = nIC;
        
        // Check IC_flag
        Random rand = new Random();
        allIC = new int[mIC][n];
        for(int i=0; i < mIC; i++)
        {
            for(int m = 0; m < n; m++)
            {
                allIC[i][m] = rand.nextInt(2);
            }
        }
        return allIC;
    }

    /* Generate rules */
    public int[][] ruleGenerate(final int r, int numRules)
    {
        int ruleLength = (int)Math.pow(2.,(double)(2*r+1));
        int[][] allRules;
        
        Random rand = new Random();
        allRules = new int[numRules][ruleLength];
        for(int k = 0; k < numRules; k++)
        {
            for(int l = 0; l < ruleLength; l++)
            {
                allRules[k][l] = rand.nextInt(2);
            }
        }
        return allRules;
    }
    
    public int[][] allRuleGenerate(final int r)
    {
        // Define size of rules: (2r+1) bits, 2^(2r+1) combinations, therefore 2^2^(2r+1) rules
        int ruleLength = (int)Math.pow(2.,(double)(2*r+1));
        int[][] allRules;
        int numRules = 10;
        
        // If rule-length is small enough, generate all rules
        if( ruleLength <= 16 )
        {
            System.out.print("\nTotally 2^"+ruleLength+" rules exist, generate all....\n");
            numRules = (int)Math.pow(2.,(double)(ruleLength));
            allRules = new int[numRules][ruleLength];
            for(int k = 0; k < numRules; k++)
            {
                allRules[k] = intToBitArray(ruleLength,k);
            }
        // If rule-length is too large, randomly generate rules
        } else {
            System.out.print("\nTotally 2^"+ruleLength+" rules exist. It is too big for indexing, randomly generate "+numRules+" instead\n");
            Random rand = new Random();
            allRules = new int[numRules][ruleLength];
            for(int k = 0; k < numRules; k++)
            {
                for(int l = 0; l < ruleLength; l++)
                {
                    allRules[k][l] = rand.nextInt(2);
                }
            }
        }
        return allRules;
    }
    
    /* Apply a rule to a configuration */
    // Update procedure:
    //  1. Extract sub-bit-array
    //  2. Look up for new site state by sub-array
    //  3. Insert output bit to new configuration
    public int[] ruleApply(final int r, final int[] rule, final int[] config)
    {
        final int confL = config.length;
        final int subL  = 2 * r + 1;
        int[] newConfig = new int[confL];
        int[] subArray = new int[subL]; 
        
        // Check: rule length == 2^subL
        if (rule.length!=(int)Math.pow(2.,(double)subL))
        {
            System.out.println("\nRule-length and r do not match, rule can not be applied!");
            System.exit(1);
            //return config;
        }
        
        // Make up a periodic configuration by copying r bits to both side
        int[] pConfig = new int[confL+2*r];
        //   0 ~ r-1: left side read from right end
        for(int i=0; i<r;i++) {pConfig[i] = config[confL-r+i];}
        //  r ~ confL-r: regular
        for(int i=r; i<(confL+r);i++) {pConfig[i] = config[i-r];}
        // confL-r ~ confL: right side read from left end
        for(int i=(confL+r); i<(confL+2*r);i++)  {pConfig[i] = config[(i-confL-r)];}
        
        // Update
        int newSiteIdx;
        for(int j = 0; j < confL; j++)
        {
            // Extract sub-bit-array
            for(int k = 0; k < subL; k++)
            {
                subArray[k] = pConfig[j+k];
            }
            // Look up for output bit
            newSiteIdx = bitArrayToInt(subArray);
            // Insert the output bit to new configuration
            newConfig[j] = rule[newSiteIdx];
        }
        
        // Return new configuration
        return newConfig;
    }

    /* Check convergence of a rule-configuration pair */
    public int[] checkConvergence(final int r, final int maxStep, 
                                  final int[] rule, final int[] config)
    {
        int[] convgMsg = new int[2];
        int step = 0;
        int cfgL = config.length;
        
        // 
        int sum;
        int[] newConfig = new int[cfgL];
        int[] tmpConfig = copyIntArray(config);
        while(step <= maxStep)
        {
            // Apply rule to current configuration
            newConfig = ruleApply(r,rule,tmpConfig);
            
            // Check convergence
            sum = sumIntArray(newConfig);
            if((sum==0)||(sum==cfgL))
            {
                convgMsg[0] = (int)(sum/cfgL);
                convgMsg[1]++;
                break;
            }
            // Check if rule change configuration at all
            if(isTwoConfigEqual(tmpConfig,newConfig))
            {
                convgMsg[0] = -1;
                break;
            }
            // For next iteration
            tmpConfig = copyIntArray(newConfig);
            step++;
            convgMsg[1] = step;
        }
        
        if(convgMsg[1] > maxStep)
            convgMsg[0] = 2;
            
        // Return convergence message:
        // -1: rule does not affect configuration any more
        //  0: converge to 0 at Mth step
        //  1: converge to 1 at Mth step
        //  2: no convergence till maxStep
        return convgMsg;
    }
    
//----------------------------------------------------------------------
// Supplemental methods: data-type convertion
//----------------------------------------------------------------------
    /* Convert a integer to a bit-string (stored in a int-string) */
    public int[] intToBitArray(final int bitLength, final int x)
    {
        int[] bitArray = new int[bitLength];
        int tmp = x;
        // Convert i into n-bit binary string
        for(int j=bitLength; j>0; j--)
        {
            bitArray[j-1] = tmp%2;  // If the remainder is 1, then this bit is 1
            tmp = tmp/2;            // divided by 2 and drop remainder, to move one bit left-ward
        }
        return bitArray;
    }

    /* Convert a bit-string (stored in a int-string) to an integer*/
    public int bitArrayToInt(final int[] bitArray)
    {
        int x = 0;
        int bl = bitArray.length;
        // Convert bitArray to an integer:
        //   x = 2^n*bitArray[0] + 2^(n-1)*bitArray[1] +....+ 2^0*bitArray[n]
        for(int j = 0; j < bl; j++)
        {
            x += bitArray[j]* (int)Math.pow(2.,(double)(bl-j-1));  
        }
        return x;
    }


    /* Check if two integer arrays are equal */
    public boolean isTwoConfigEqual(final int[] conf1, final int[] conf2)
    {
        // Check: 2 config should have the same length
        if (conf1.length!=conf2.length)
        {
            System.out.println("\nLength of two configurations are not the same, can not be compared!");
            return false;
        }

        boolean output = true;
        for (int i = 0; i < conf1.length; i++){
            if (conf1[i]!=conf2[i])
            {
                output = false;
                break;
            }
        }
        return(output);
    }

    /* Copy integer array */
    public int[] copyIntArray(final int[] a1)
    {
        int[] a2 = new int[a1.length];
        for (int i = 0; i < a1.length; i++){
            a2[i] = a1[i];
        }
        return(a2);
    }

    /* Sum up integer array */
    public int sumIntArray(final int[] a1)
    {
        int sum = 0;
        for (int i = 0; i < a1.length; i++){
            sum += a1[i];
        }
        return(sum);
    }
}
//----------------------------------------------------------------------
}
